package com.dyz.leetcode;

import java.util.HashMap;

public class Rob337 {
    //    //技巧型，(1)root选，下两个节点不选，下下节点选，递归   (2) root不选， 下两个节点选，下下两个节点不选， 超时
    //    public int rob(TreeNode root) {
    //
    //        if(root==null){return 0;}
    //        int res1 = root.val;
    //        if(root.left!=null){
    //            res1+=rob(root.left.left)+rob(root.left.right);
    //        }
    //        if(root.right!=null){
    //            res1+=rob(root.right.left)+rob(root.right.right);
    //        }
    //        int res2 = 0;
    //        res2+=rob(root.left)+rob(root.right);
    //        return Math.max(res1,res2);
    //    }

    //技巧型，(1)root选，下两个节点不选，下下节点选，递归   (2) root不选， 下两个节点选，下下两个节点不选 --》剪枝
//    public int rob(TreeNode root){
//        if(root==null){return 0;}
//        HashMap<TreeNode, Integer> map = new HashMap<>();
//        rob(root, map);
//        return map.get(root);
//    }
//    public int rob(TreeNode root, HashMap<TreeNode, Integer> map) {
//
//        if(root==null){return 0;}
//        //是否使用过
//        if(map.containsKey(root)){return map.get(root);}
//        int res1 = root.val;
//        if(root.left!=null){
//            res1+=rob(root.left.left, map)+rob(root.left.right, map);
//        }
//        if(root.right!=null){
//            res1+=rob(root.right.left,map)+rob(root.right.right, map);
//        }
//        int res2 = 0;
//        res2+=rob(root.left, map)+rob(root.right, map);
//        int res =Math.max(res1,res2);
//        map.put(root,res);
//        return res;
//    }

    //动态规划
    public int rob(TreeNode root){
        int [] res = helper(root);
        return Math.max(res[0], res[1]);
    }

   public int[] helper(TreeNode root){
        // res[0] : 不选 不rob
        //  res[1]: 选 rob
        int [] res = new int[2];
        if(root==null){return res;}
        int [] left = helper(root.left);
        int [] right = helper(root.right);

        //root
       res[0] = 0 + Math.max(left[0], left[1]) + Math.max(right[0],right[1]);
       res[1] = root.val +left[0]+right[0];

        return res;
   }



}
